package Offer06_从尾到头打印链表;

import java.util.*;

/**
 * ----------------------------------------------------------------
 * 题目：
 *      输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
 * ----------------------------------------------------------------
 * 示例：
 *      输入：head = [1,3,2]
 *      输出：[2,3,1]
 * ----------------------------------------------------------------
 * 方法：
 *      方法1：反转数组
 *      方法2：递归
 *      方法3：模拟栈
 *      方法4：栈
 * ----------------------------------------------------------------
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}
class Solution {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(2);
        node1.next=node2;
        node2.next=node3;
        ListNode head1 = node1;
        ListNode head2 = node1;
        ListNode head3 = node1;
        ListNode head4 = node1;
        System.out.println(Arrays.toString(reversePrint1(head1)));
        System.out.println(Arrays.toString(reversePrint2(head2)));
        System.out.println(Arrays.toString(reversePrint3(head3)));
        System.out.println(Arrays.toString(reversePrint4(head4)));
    }
    static List<Integer> list;
    public static int[] reversePrint1(ListNode head) {
        list=new ArrayList<>();
        while(head!=null){
            list.add(head.val);
            head=head.next;
        }
        int[] ans = new int[list.size()];
        for(int i=0;i<ans.length;++i){
            ans[i]=list.get(i);
        }
        reverse(ans);
        return ans;
    }
    public static void reverse(int[] array) {
        int i = 0;
        int j = array.length - 1;
        while (i < j) {
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
            ++i;
            --j;
        }
    }

    static List<Integer> list2;
    public static int[] reversePrint2(ListNode head) {
        list2=new ArrayList<>();
        dfs(head);
        int[] ans = new int[list2.size()];
        for(int i=0;i<ans.length;++i){
            ans[i]=list2.get(i);
        }
        return ans;
    }
    public static void dfs(ListNode node){
        if(node==null){
            return;
        }
        dfs(node.next);
            list2.add(node.val);
    }

    public static int[] reversePrint3(ListNode head) {
        ListNode ret = head;
        int count=0;
        while(ret!=null){
            ret=ret.next;
            count++;
        }
        int[] ans = new int[count];
        int i=count-1;
        while(head!=null){
            ans[i]=head.val;
            head=head.next;
            i--;
        }
        return ans;
    }

    public static int[] reversePrint4(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        while(head!=null){
            stack.push(head.val);
            head=head.next;
        }
        int[] ans = new int[stack.size()];
        int i=0;
        while(!stack.isEmpty()){
            ans[i]=stack.pop();
            ++i;
        }
        return ans;
    }
}
